package com.dhnsoft.数据结构与算法.链表;

/**
 * ClassName: SingleLinkedListDemo2
 * Package: com.dhnsoft.数据结构与算法.链表
 * Description:
 *
 * @Author dhn
 * @Create 2024/3/5 16:17
 * @Version 1.0
 */
public class SingleLinkedListDemo2 {
    public static void main(String[] args) {
        SingleLinked s1 = new SingleLinked();
        Node n1 = new Node(1,"张三");
        Node n2 = new Node(3,"李四");
        Node n3 = new Node(5,"王五");
        s1.addByOrder(n1);
        s1.addByOrder(n2);
        s1.addByOrder(n3);
        System.out.println("第一组---");
        s1.list();

        SingleLinked s2 = new SingleLinked();
        Node n4 = new Node(2,"张三");
        Node n5 = new Node(4,"李四");
        Node n6 = new Node(6,"王五");
        s2.addByOrder(n4);
        s2.addByOrder(n5);
        s2.addByOrder(n6);
        System.out.println("第二组---");
        s2.list();

        Node node = mergeList(s1, s2);
        list(node);

//        Node n4 = new Node(2,"李六");
//        s1.update(n4);
//        System.out.println("更新后---");
//        s1.list();
//
//        s1.delete(n4);
//        System.out.println("删除后---");
//        s1.list();

//        int len = getLen(s1.getHead());
//        System.out.println("当前链表的长度为："+len);
//        Node lastkNode = getLastkNode(s1.getHead(), 2);
//        System.out.println("当前节点为:"+lastkNode);

//        reverseList(s1.getHead());
//        System.out.println("反转之后的节点如下:");
//        s1.list();



    }

    //根据node遍历出来数据
    public static void list(Node node){
        if(node.next==null){
            return;
        }
        while (node.next!=null){
            System.out.println(node);
            node = node.next;
        }
    }

    public static Node mergeList(SingleLinked h1,SingleLinked h2){
        if(h1==null){
            return h2.getHead();
        }
        if(h2==null){
            return h1.getHead();
        }
        if(h1==null&&h2==null){
            return null;
        }
        Node newNode = new Node(0,"");
        Node temp = newNode;
        Node t1 = h1.getHead().next;
        Node t2 = h2.getHead().next;
        while(t1!=null&&t2!=null){
            if(t1.no>t2.no){
                temp.next = t2;
                t2 = t2.next;
            }
            else{
                temp.next = t1;
                t1 = t1.next;
            }
            temp = temp.next;
        }
        if(t1==null){
            temp.next = t2;
        }
        if(t2==null){
            temp.next = t1;
        }
        return newNode;
    }

    //方法：获取到单链表的节点个数（如果是带头节点的链表，需求不统计头节点）
    public static int getLen(Node node){
        if(node.next==null){
            return 0;
        }
        Node temp = node.next;
        int num = 0;
        while (temp!=null){
            num++;
            temp = temp.next;
        }
        return num;
    }

    //查找单链表中的倒数第k个节点
    public static Node getLastkNode(Node node, int index){
        if(node.next==null){
            System.out.println("当前链表为空");
            return null;
        }
        Node temp = node;
        int len = getLen(node)-index;
        for (int i = 0 ;i<=len;i++){
            temp = temp.next;
        }
        return temp;
    }

    //将单链表进行反转
    public static void reverseList(Node node){
        if(node.next==null||node.next.next==null){
            return;
        }
        Node cur = node.next;
        Node next = null;//定义一个当前节点来保存后面的节点
        Node newList = new Node(0,"");//定义一个新节点
        while (cur!=null){
            next = cur.next;
            cur.next = newList.next;
            newList.next = cur;
            cur = next;
        }
        node.next = newList;
    }
}

class SingleLinked{
    private Node head = new Node(0,"");
    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    //添加并有序插入到合适的位置使其有序
    public void addByOrder(Node node){
        //声明一个动态指针来获取适合插入的地方
        Node temp = head;
        boolean flag = false;
        while (true){
            if(temp.next==null){
                break;
            }
            //如果当前节点的下一个节点的no大于要插入的节点证明适合插入
            if(temp.next.no>node.no){
                break;
            }
            else if(temp.no==node.no){//还有一种情况就是当前节点的no等于要插入节点的no，这时就是插入重复，则不需要插入
                flag=true;
            }
            temp = temp.next;
        }
        if(flag){
            System.out.printf("重复插入no为%d的节点",node.no);
            return;
        }
        else{
            node.next = temp.next;
            temp.next = node;
        }
    }

    //查询出单链表集合
    public void list(){
        if(head.next==null){
            System.out.println("当前链表为空");
            return;
        }
        Node temp = head.next;
        while (temp!=null){
            System.out.println(temp);
            temp = temp.next;
        }
    }


    //更新某一个节点
    public void update(Node node){
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        Node temp = head.next;
        boolean flag = false;
        while(temp!=null){
            if(temp.no==node.no){
                temp.name = node.name;
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(!flag){
            System.out.printf("未找到no为%d的节点\n",node.no);
        }
    }

    //删除某一个节点
    public void delete(Node node){
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        Node temp = head;
        boolean flag = false;
        while (temp.next!=null){
            if(temp.next.no==node.no){
                flag = true;
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next;
        }
        if(!flag){
            System.out.printf("未找到no为%d的节点\n",node.no);
        }
    }
}

class Node{
    int no;
    String name;
    Node next;
    public Node(int no,String name){
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                "" +
                '}';
    }
}
